/**
 * Created with JetBrains PhpStorm.
 * User: ishowshao
 * Date: 12-8-29
 * Time: 下午10:36
 */
//以下为测试代码
var array = [];
for (var x = 0; x < 1000000; x++) {
    array.push(x + 1);
}
function shuffle() {
    return Math.random() - 0.5;
}
array.sort(shuffle);
array.sort(shuffle);
//console.log(array.join(','));

console.log(array);

var flashSort = function () {
    var i;
    var j;
    var k = 0;
    var anmin = array[0];
    var nMax = 0;
    var n = array.length;
    var m = n / 20;
    if (m < 30) {
        m = 30;
    }
    var l = [];
    for (var x = 0; x < m; x++) {
        l.push(0);
    }

    for (i = 1; i < n; i++) {
        if (array[i] < anmin) {
            anmin = array[i];
        }
        if (array[i] > array[nMax]) {
            nMax = i;
        }
    }

    if (anmin == array[nMax]) {
        return;
    }

    var c1 = (m - 1) / (array[nMax] - anmin);

    for (i = 0; i < n; i++) {
        k = Math.floor(c1 * (array[i] - anmin));
        l[k]++;
    }

    for (k = 1; k < m; k++) {
        l[k] += l[k - 1];
    }

    var hold = array[nMax];
    array[nMax] = array[0];
    array[0] = hold;


    var nmove = 0;
    var flash;
    j = 0;
    k = m - 1;


    while (nmove < n - 1) {
        while (j > (l[k] - 1)) {
            j++;
            k = Math.floor(c1 * (array[j] - anmin));
        }

        flash = array[j];

        while (!(j == l[k])) {
            k = Math.floor(c1 * (flash - anmin));

            hold = array[l[k] - 1];
            array[l[k] - 1] = flash;
            flash = hold;

            l[k]--;
            nmove++;
        }
    }

    var insertionSort = function () {
        var i, j, hold;

        for (i = array.length - 3; i >= 0; i--) {
            if (array[i + 1] < array[i]) {
                hold = array[i];
                j = i;

                while (array[j + 1] < hold) {
                    array[j] = array[j + 1];
                    j++;
                }

                array[j] = hold;
            }
        }
    };

    insertionSort();
};

var array2 = [];
for (var i = 0; i < array.length; i++) {
    array2.push(array[i]);
}

console.log(array2);
var st = +new Date();
array2.sort(function (a, b) {
    return a - b;
});
console.log(+new Date() - st);
console.log(array2);

var begin = +new Date();
flashSort();
console.log(+new Date() - begin);
//console.log(array.join(','));
console.log(array);
